package com.LeeCode;

/**
 * 目标和
 */

public class Code494 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 5;
        System.out.println(new Code494().findTargetSumWays(nums, target));
    }

    private int ans = 0;

    public int findTargetSumWays(int[] nums, int target) {
        backtrace(nums, 0, 0, target);
        return ans;
    }

    private void backtrace(int[] nums, int index, int sum, int target) {
        if (index == nums.length) {
            ans += sum == target ? 1 : 0;
            return;
        }
        backtrace(nums, index + 1, sum + nums[index], target);
        backtrace(nums, index + 1, sum - nums[index], target);
    }
}
